//从根节点到叶节点的路径数字之和
class Solution {
public:
    //vector<int>nums;
    int res=0;
    int sumNumbers(TreeNode* root) 
    {
        if(!root) return 0;
        inorder(root,0);
        // int res=0;
        // for(auto e:nums) res+=e;
        return res;
    }
    void inorder(TreeNode* root,int prenum)
    {
        int val=prenum*10+root->val;
        if(root->left)  inorder(root->left,val);
        if(root->right) inorder(root->right,val);
        if(!root->left && !root->right)
        {
            //nums.push_back(val);
            res+=val;
        }
    }
};
//向下的路径节点之和
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) 
    {
        //因为本题是可以不从根节点开始的
        //假如写了process是用来统计 从根节点开始路径和等于targetSum的函数
        //那应该 嵌套进行调用这个函数
        if(!root) return 0;
        int res=0;
        res+=process(root,targetSum);
        res+=pathSum(root->left,targetSum);
        res+=pathSum(root->right,targetSum);
        return res;
    }
    int process(TreeNode* root,long long targetSum)
    {
        if(!root) return 0;
        int tmp=0;
        if(root->val==targetSum) tmp++;
        tmp+=process(root->left,targetSum-root->val);
        tmp+=process(root->right,targetSum-root->val);
        return tmp;
    }
};
//展平二叉搜索树
class Solution {
public:
    vector<int>v;
    TreeNode* increasingBST(TreeNode* root) 
    {
        if(!root) return nullptr;

        TreeNode* phead=new TreeNode(-1);
        TreeNode* cur=phead;
        preorder(root);
        for(auto val:v)
        {
            TreeNode* node=new TreeNode(val);
            cur->right=node;
            cur=cur->right;
        }
        return phead->right;
    }
    void preorder(TreeNode* root)
    {
        if(!root) return;
        preorder(root->left);
        v.push_back(root->val);
        preorder(root->right); 
    }
};
//二叉搜索树中的中序后继
class Solution {
public:
    TreeNode* res;
    TreeNode* prefix=nullptr;
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) 
    {
        //思路 中序遍历 使用一个变量记录当前节点的前一个节点
        //当 当前的节点的前一个节点==p时 记录当前节点
        fun(root, p);
        return res;
    }
    void fun(TreeNode* root, TreeNode* p) 
    {
        if(!root) return;
        fun(root->left, p);
        if (prefix == p) res = root;
        prefix = root;
        fun(root->right, p);    
    }
};
//所有大于等于节点的值之和
class Solution {
public:
    int sum=0;
    TreeNode* convertBST(TreeNode* root) 
    {
        if(!root) return nullptr;
        dfs(root);
        return root;
    }
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root->right);
        sum+=root->val;
        root->val=sum;
        dfs(root->left);
    }
};
// 二叉搜索树中两个节点之和
class Solution {
public:
    vector<int>nums;
    bool findTarget(TreeNode* root, int k) 
    {
        if(!root) return false;
        process(root);
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int tmp=nums[l]+nums[r];
            if(tmp>k) r--;
            else if(tmp==k) return true;
            else l++;
        }
        return false;
    }
    void process(TreeNode* root)
    {
        if(!root) return;
        process(root->left);
        nums.push_back(root->val);
        process(root->right);
    }

};
//最长连续序列
class Solution {
public:
    int longestConsecutive(vector<int>& nums) 
    {
      //存到hash里面 只要是连续序列 不管我起始点在哪里 一定可以找到他数值+1
      //或者-1的数字   用哈希找遍历元素的前一个是否存在 直到找不到
      //然后向后找 直到不存在 更新一下长度
        if(nums.empty()) return 0;
        int res=1;
        unordered_set<int>hash;// -> 数字 数字
        for(auto e:nums)
        {
            hash.insert(e);
        }
        while(hash.size())
        {
            int cur=*hash.begin();
            hash.erase(cur);
            int next=cur+1;
            while(hash.count(next))
            {
                hash.erase(next);
                next++;
            }
            int prev=cur-1;
            while(hash.count(prev))
            {
                hash.erase(prev);
                prev--;
            }
            res=max(res,next-prev-1);
        }
        return res;
    }
};